

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:

    const int dir[4][2] = {{1,  0},
                           {0,  1},
                           {-1, 0},
                           {0,  -1}};

    vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> res(m, vector<int>(n, 0));
        vector<vector<bool>> flag(m, vector<bool>(n, false));

        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    flag[i][j] = true;
                    q.emplace(i, j);
                }
            }
        }

        while (!q.empty()) {
            auto[r, c] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int mx = r + dir[i][0], my = c + dir[i][1];
                if (mx >= 0 && mx < m && my >= 0 && my < n && !flag[mx][my]) {
                    res[mx][my] = res[r][c] + 1;
                    flag[mx][my] = true;
                    q.emplace(mx, my);
                }
            }
        }

        return res;
    }
};

int main() {

    vector<vector<int>> mat = {{0, 0, 0},
                               {0, 1, 0},
                               {1, 1, 1}};

    Solution solution;
    auto res = solution.updateMatrix(mat);
    for (auto i: res) {
        for (auto j: i) {
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}